package com.xjh.basestudy.algorithmandexercise.sort;

/*
冒泡排序
* 它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误
就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二
氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
冒泡排序算法的原理如下：
1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的
数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。*/
public class BubbleSort {
/*    public int[] sort(int[] array) {
        int temp = 0;
        // 外层循环，它决定一共走几趟 //-1为了防止溢出
        for (int i = 0; i < array.length - 1; i++) {//n个元素比较n-1趟,从0开始,所以length要-1
         //通过符号位可以减少无谓的比较，如果已经有序了，就退出循环
            int flag = 0;
        //内层循环，它决定每趟走几次
            for (int j = 0; j < array.length - i - 1; j++) {//每个元素和只其后面的元素比较
                // 如果后一个大于前一个,则换位
                if (array[j + 1] > array[j]) {
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    flag = 1;
                }
            }
            //如果内层循环执行完一趟后,flag还是=0,
            // 说明后面的排序已经是有序的了,不用再执行外层循环了,直接跳出
            if(flag == 0){
                break;
            }
        }
 return array;
    }


    public static void main(String[] args) {
        BubbleSort bubble = new BubbleSort();
        int[] array = {2,5,1,6,4,9,8,5,3,1,2,0};
        int[] sort = bubble.sort(array);
        for (int num:sort){
            System.out.print(num+"\t");
        }
    }*/

//练习一遍
    //冒泡要点:双层循环,n-1趟,交换位置
public int[] sort(int[] array){
    int temp = 0;
    for (int i = 0; i < array.length-1 ; i++) {
        int flag = 0;
        for (int j = 0; j < array.length - i -1 ; j++) {
            if(array[j]<array[j+1]){
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }

        }
        if(flag == 0){
            break;
        }

    }
    return array;
}

    public static void main(String[] args) {
        BubbleSort bubble = new BubbleSort();
        int[] array = {4,5,2};
        int[] sorted = bubble.sort(array);
        for (int i : sorted) {
            System.out.println(i);

        }


    }
}

